package com.leetcode.tree.recursion;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/6/15 20:51
 */
public class PathSum_437 {

    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        /**
         * 1.以根节点为root求存在的分支数
         * 2.分别将左子树和右子树求其满足的路径数，相加求总和
         */
        int ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
        return ret;
    }

    private int pathSumStartWithRoot(TreeNode root, int sum) {
        // root为空时，说明没有路径
        if (root == null) return 0;
        int ret = 0;
        // 当sum和当前结点的值相等则记录 -- 因为不一定是leaf结点
        if (root.val == sum) ret++;
        // 分别记录左右子树作为根节点时向下遍历的路径条数
        // 关键点 --- 假定存在，那么向下遍历时则需要在此基础上减去对应值
        ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
        return ret;
    }

    private int pathSumStartWithRoot1(TreeNode root, int sum) {
        if (root == null) return 0;
        int ret = sum == root.val ? 1 : 0;
        ret += pathSumStartWithRoot1(root.left, sum - root.val) + pathSumStartWithRoot1(root.right, sum - root.val);
        return ret;
    }

    public int pathSum1(TreeNode root, int sum) {
        return pathSum(root, sum, new int[1000], 0);
    }

    // 第二种解法！！ 有待理解
    // 用一个数组来记忆当前路径，避免重复计算
    // 1.以当前结点为最终叶子结点向上追溯，
    // 2.路径上的任一结点为根节点到当前结点的路径和为sum的路径个数。
    // 3.然后以同样的方法以自己的孩子结点为最终叶子结点计算。
    public int pathSum(TreeNode root, int sum, int[] array/*保存路径*/, int p/*指向路径终点*/) {
        if (root == null) return 0;
        int n = sum == root.val ? 1 : 0;
        int temp = root.val;
        for (int i = p - 1; i >= 0; i++) {
            temp += array[i];
            // 在之前的路径中还存在sum，则n++
            if (temp == sum) n++;
        }
        // 记录当前路径重点的root值
        array[p] = root.val;
        int n1 = pathSum(root.left, sum, array, p + 1);
        int n2 = pathSum(root.right, sum, array, p + 1);
        return n + n1 + n2;
    }


}
